package kyssion.leetcode.num1_50;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class code46_全排列 {

    public static void main(String[] args) {
        System.out.println(new code46_全排列().permute2(
                new int[]{
                }
        ));
    }

    /**
     * 第一种解法,使用暴利递归的方法
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        boolean[] isUse = new boolean[nums.length];
        Stack<Integer> stack = new Stack<>();
        List<List<Integer>> listList = new ArrayList<>();
        ans(nums, 0, isUse, listList, stack);
        return listList;
    }

    public void ans(int[] nums, int index, boolean[] isUse, List<List<Integer>> lists, Stack<Integer> state) {
        if (index == nums.length) {
            lists.add(new ArrayList<>(state));
            return;
        }
        for (int a = 0; a < nums.length; a++) {
            if (!isUse[a]) {
                isUse[a] = true;
                state.push(nums[a]);
                ans(nums, index + 1, isUse, lists, state);
                state.pop();
                isUse[a] = false;
            }
        }
    }

    /**
     * 想到 1,2 的全排列只是 1,2 和 2,1
     * 所以其实我们只有不停的遍历这个方法就好了
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute2(int[] nums) {
        boolean[] isUse = new boolean[nums.length];
        List<List<Integer>> listList = new ArrayList<>();
        ans(nums, 0, listList);
        return listList;
    }

    public void ans(int[] nums, int index, List<List<Integer>> lists) {
        if (index == nums.length) {
            List<Integer> list = new ArrayList<>();
            for (int a = 0; a < nums.length; a++) {
                list.add(nums[a]);
            }
            lists.add(list);
            return;
        }
        int exchange = 0;
        for (int a = index; a < nums.length; a++) {
            exchange = nums[a];
            nums[a] = nums[index];
            nums[index] = exchange;
            ans(nums, index + 1, lists);
            exchange = nums[a];
            nums[a] = nums[index];
            nums[index] = exchange;
        }
    }
}
